package com.cty.twentiethDay;
/*
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
*/
public class Q_27 {
    public static void main(String[] args) {

    }

    //暴力算法
    /*
    * 时间复杂度O(m + n)
    * 空间复杂度O(1)
    * */
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode listNode = new ListNode(-1);
        ListNode temp1 = list1;
        ListNode temp2 = list2;
        ListNode temp3 = listNode;
        while (temp1 != null && temp2 != null) {
            if (temp1.val > temp2.val) {
                temp3.next = temp2;
                temp2 = temp2.next;
            } else {
                temp3.next = temp1;
                temp1 = temp1.next;
            }
            temp3 = temp3.next;
        }
        if (temp1 == null) {
            temp3.next = temp2;
        }
        if (temp2 == null) {
            temp3.next = temp1;
        }
        temp3 = listNode.next;
        listNode.next = null;
        return temp3;
    }

    //递归
    /*
    * 时间复杂度O(m + n)
    * 空间复杂度O(m + n)
    * */
    public static ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val > list2.val) {
            list2.next = mergeTwoLists2(list1,list2.next);
            return list1;
        } else {
            list1.next = mergeTwoLists2(list1.next,list2);
            return list2;
        }
    }
}
